package com.clps.algorithm.chapter06.矩阵中最大的矩形;

import java.util.Stack;

/**
 * 请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如在图6.6的矩阵中，最大的只包含1的矩阵如阴影部分所示，它的面积是6。
 */
public class demo01 {
    public static void main(String[] args) {

    }

    public  int maximaRectangle(char[][] matrix){
        if(matrix.length ==0 || matrix[0].length ==0){
            return  0;
        }

        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (char[] row : matrix) {
            for (int i = 0; i < row.length; i++) {
                if(row[i] == '0'){
                    heights[i] = 0;
                }else{
                    heights[i]++;
                }
            }

            maxArea = Math.max(maxArea,largestRectangleArea(heights));
        }
        return  maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        int maxArea = 0;

        for (int i = 0; i <heights.length ; i++) {
            while (stack.peek()!=-1 && heights[stack.peek()]>=heights[i]){
                int height = heights[stack.pop()];
                int width = i - stack.peek()-1;
                maxArea = Math.max(maxArea,height * width);
            }
            stack.push(i);
        }

        while (stack.peek()!=-1){
            int height = heights[stack.peek()-1];
            int width = heights.length - stack.peek()-1;
            maxArea = Math.max(maxArea,height* width);
        }
        return  maxArea;
    }

}
